package main.Q1501_1600;

import java.util.Map;
import java.util.TreeMap;

public class Q1561_1570 {
    public static void main(String[] args) {
        System.out.println("Question1561：");
        System.out.println("Question1562：查找大小为M的最新分组");
        System.out.println("Question1563：");
        System.out.println("Question1564：");
        System.out.println("Question1565：");
        System.out.println("Question1566：");
        System.out.println("Question1567：乘积为正数的最长子数组长度");
        System.out.println("Question1568：");
        System.out.println("Question1569：");
        System.out.println("Question1570：");
    }
}

class Question1562{
    public int findLatestStep(int[] arr, int m) {
        if (arr.length == m) return m;
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        tm.put(0, arr.length + 1);
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            Map.Entry<Integer, Integer> entry = tm.floorEntry(num);
            int l = entry.getKey(), r = entry.getValue();
            if (num - l - 1 == m) {
                return i;
            }
            if (r - num - 1 == m) {
                return i;
            }
            tm.put(l, num);
            tm.put(num, r);
        }
        return -1;
    }
}

class Question1567{
    public static int getMaxLen(int[] nums) {
        int length= nums.length,maxLength=0;
        int[] plus=new int[length],minus=new int[length];//以i为结尾的最长累乘为正数长度和累乘为负数长度
        if (nums[0]>0) plus[0]=1;//初始化第一个元素
        else if (nums[0]<0) minus[0]=1;
        maxLength=plus[0];
        for (int i=1;i<length;i++){
            if (nums[i]>0){//当前元素为正数
               plus[i]=plus[i-1]+1;//之前正数累乘长度
               minus[i]=minus[i-1]>0 ? minus[i-1]+1 : 0;//负数再累乘一个正数还是负数
            }else if (nums[i]<0){
                minus[i]=plus[i-1]+1;
                plus[i]= minus[i-1]>0 ? minus[i-1]+1 : 0;
            }else {
                plus[i]=0;
                minus[i]=0;
            }
            maxLength=Math.max(maxLength,plus[i]);
        }
        return maxLength;
    }
}